Market adoption of wireless LAN (WLAN) technology has exploded, as users from a wide range of backgrounds and vertical industries have brought this technology into their homes, offices, and increasingly into the public air space. This inflection point has highlighted not only the limitations of earlier-generation systems, but the changing role WLAN technology now plays in people's work and lifestyles, across the globe. Indeed, WLANs are rapidly changing from convenience networks to business-critical networks. Increasingly users are depending on WLANs to improve the timeliness and productivity of their communications and applications, and in doing so, require greater visibility, security, management, and performance from their network.
The rapid proliferation of lightweight, portable computing devices and high-speed WLANs enables users to remain connected to various network resources, while roaming throughout a building or other physical location. The mobility afforded by WLANs has generated a lot of interest in applications and services that are a function of a mobile user's physical location. Examples of such applications include: printing a document on the nearest printer, locating a mobile user or rogue access point, displaying a map of the immediate surroundings, and guiding a user inside a building. The required or desired granularity of location information varies from one application to another. Indeed, the accuracy required by an application that selects the nearest network printer, or locates a rogue access point, often requires the ability to determine in what room a wireless node is located. Accordingly, much effort has been dedicated to improving the accuracy of wireless node location mechanisms.
The use of radio signals to estimate the location of a wireless device or node is known. For example, a Global Positioning System (GPS) receiver obtains location information by triangulating its position relative to four satellites that transmit radio signals. The GPS receiver estimates the distance between each satellite based on the time it takes for the radio signals to travel from the satellite to the receiver. Signal propagation time is assessed by determining the time shift required to synchronize the pseudo-random signal transmitted by the satellite and the signal received at the GPS receiver. Although triangulation only requires distance measurements from three points, an additional distance measurement from a fourth satellite is used for error correction.
The distance between a wireless transmitter and a receiver can also be estimated based on the strength of the received signal, or more accurately the observed attenuation of the radio signal. Signal attenuation refers to the weakening of a signal over its path of travel due to various factors like terrain, obstructions and environmental conditions. Generally speaking, the magnitude or power of a radio signal weakens as it travels from its source. The attenuation undergone by an electromagnetic wave in transit between a transmitter and a receiver is referred to as path loss. Path loss may be due to many effects such as free-space loss, refraction, reflection, and absorption.
In business enterprise environments, most location-tracking systems are based on RF triangulation or RF fingerprinting techniques. RF triangulation calculates a mobile user's location based upon the detected signal strength of nearby access points (APs). It naturally assumes that signal strength is a factor of proximity, which is true a majority of the time. However, the multipath phenomenon encountered in indoor RF environments does present certain difficulties in locating wireless nodes, since reflection and absorption of RF signals affects the correlation between signal strength and proximity. RF fingerprinting compares a mobile station's view of the network infrastructure (i.e., the strength of signals transmitted by infrastructure access points) with a database that contains an RF physical model of the coverage area. This database is typically populated by either an extensive site survey or an RF prediction model of the coverage area. For example, Bahl et al., “A Software System for Locating Mobile Users: Design, Evaluation, and Lessons,” http://research.microsoft.com/˜bahl/Papers/Pdf/radar.pdf, describes an RF location system (the RADAR system) in a WLAN environment, that allows a mobile station to track its own location relative to access points in a WLAN environment.
The RADAR system relies on a so-called Radio Map, which is a database of locations in a building and the signal strength of the beacon packets emanating from the access points as observed, or estimated, at those locations. For example, an entry in the Radio Map may look like (x, y, z, ssi(i=1 . . . n)), where (x, y, z) are the physical coordinates of the location where the signal is recorded, and ssi is the signal strength of the beacon signal emanating from the ith access point. According to Bahl et al., Radio Maps may be empirically created based on heuristic evaluations of the signals transmitted by the infrastructure radios at various locations, or mathematically created using a mathematical model of indoor RF signal propagation. To locate the position of the mobile user in real-time, the mobile station measures the signal strength of each of access points within range. It then searches a Radio Map database against the detected signal strengths to find the location with the best match. Bahl et al. also describe averaging the detected signal strength samples, and using a tracking history-based algorithm, to improve the accuracy of the location estimate. Bahl et al. also address fluctuations in RF signal propagation by using multiple Radio Maps and choosing the Radio Map which best reflects the current RF environment. Specifically, one access point detects beacon packets from other access points and consults a radio map to estimate its location, and evaluates the estimated location with the known location. The RADAR system chooses the Radio Map which best characterizes the current RF environment, based on a sliding window average of received signal strengths.
While the RADAR system works for its intended objective, even in this system, location accuracy decreases with the error in detecting the strength of RF signals. For example, the accuracy of signal strength detection between a radio transmitter and a radio receiver whose signal strength measurements are used to estimate location, and thus, the accuracy of locating a wireless node, decreases as the detected signal strength decreases. As discussed above, the RADAR, and other RF fingerprinting, systems estimate the location of a wireless node by finding the best fit in the Radio Maps, treating the signal strength measurements associated with the different access points equally. As discussed below, however, the error injected by errors in signal strength detection can inject large amounts of error in computing the location of a wireless node, especially where the detected signal, at the radio receiver, is weak. Still further, while the RADAR system allows a mobile station to track its own location, it does not disclose a system that allows the WLAN infrastructure to track the location of wireless nodes, such as rogue access points. Such a system is desirable as it obviates the need for special client software to be installed on the mobile stations.
Moreover, individual differences as to how two different wireless nodes detect and report signal strength can cause errors in location, since the Radio Maps assume no error in such measurements. Accordingly, two wireless nodes in the same location that detect different signal strengths will compute different estimated locations. Still further, while the RADAR system allows a mobile station to track its own location, it does not disclose a system that allows the WLAN infrastructure to track the location of wireless nodes, such as rogue access points. Such a system is desirable as it obviates the need for special client software to be installed on the mobile stations.
This paradigm shift, however, presents certain problems. As discussed above, the Radio Maps in the RADAR system are constructed from the point of view of a wireless node in an RF environment that includes access points in known locations. In other words, the Radio Maps are constructed based on heuristic and/or mathematical evaluations of the propagation of signals from the access points to a wireless node at a given location. Accordingly, the RADAR system need not assume symmetry of path loss between a given location and the access points in the RADAR system, since the mobile station detects the signal strength of the access points and computes its own location. In addition, since the location of a wireless node is based on path loss, the transmit power of the radio transmitters used to determine location must also be known. In the RADAR system, this is not problematic, since the signals used to determine location are transmitted by access points, whose transmit power can be controlled or easily determined. Estimating location based on signals transmitted by a wireless node, however, can be problematic, since transmit power can vary among wireless device manufacturers, and/or may be individually configured by the mobile user.
One approach to this problem is to assume symmetry in path loss between a given location in an RF environment and the radio transceivers used to detect signals transmitted by the wireless nodes. Furthermore, these approaches also assume a uniform transmit power for the wireless nodes in light of the fact that legal regulations, as well as current chip set technology, generally places an upper limit on transmit power. These two assumptions, however, can significantly impact the accuracy of locating a wireless node. As discussed above, the RADAR system, for example, finds the location coordinates in the Radio Map that are the best fit based on the detected signal strengths. That is, for each point in the Radio Map, the location metric computes the Euclidean distance between the detected signal strength values and the values in the Radio Map.
The following equation provides an illustrative example, assume for didactic purposes that a given wireless node is detected by three access points. The signal strength samples are RSSIap1 RSSIap2, and RSSIap3, while the RF coverage maps for each of the access points are denoted as MAPap1, MAPap2, MAPap3, where the coverage maps include access point signal strength values detected or computed for different locations in a defined region. Further assume that all coverage maps have values at all locations within the search region. Again, assuming path loss symmetry and a uniform transmit power, individual error surfaces for each access point can be created based on the signal strength detected at each access point, (RSSIap1, etc.) and the signal strength values in the individual coverage maps (e.g., MAPap1, etc.). That is, the error surface is the difference between the observed signal strength at a given access point less the signal strength values in the coverage map. The locations in this coverage map where the difference is zero are generally the likely or estimated locations relative to each radio receiver. In many situations, however, the measured signal strengths, RSSIap1 RSSIap2, and RSSIap3, do not match the signal strengths recorded in the coverage maps MAPap1, MAPap2, MAPap3 at any one location. In this case, it is desirable to find the location that is “closest” to matching RSSIap1 RSSIap2, and RSSIap3—in other words, the location that minimizes some function of MAPap1, MAPap2, MAPap3, RSSIap1 RSSIap2, and RSSIap3. Bahl et al., supra, describe several ways in which this function is created, including minimum mean squared error, minimum distance, and minimum Manhattan grid distance.
Furthermore, a total error surface, ErrSurf, can be computed based on the sum of the squares (to neutralize positive and negative differences) of the individual error surfaces (i.e., the difference between the detected signal strength values and the signal strength values in each coverage maps), as follows: ErrSurf=[(RSSIap1−MAPap1)2+(RSSIap2MAPap2)2+(RSSIap3−MAPap3)2]/3. In one implementation, the estimated wireless node location is derived from the minimum or minimum of this total error surface.
However, a change in the wireless node's transmit power (or, in the RADAR system, inaccuracies in detecting signal strength by the wireless nodes) will adversely affect the accuracy of this metric. For example, a N dB difference between the actual and assumed transmit power of a wireless node would cause a N dB change in the detected signal strengths. Rather than merely shifting the individual signal strength differences for each point in the individual error surfaces up by some fixed amount, the individual differences between the detected signal strengths and the signal strength values in the error surface can change quite dramatically. Indeed, each point in the individual error surfaces are shifted an amount proportional to the dB error. This circumstance moves some areas of the total error surface up relative to others, and some areas of the total error surface down relative to others, significantly altering the shape of the error surface, as well as the location, shape, and size of its minima. It also creates unpredictable error with changes in transmit power. Similar problems will occur for a fixed error in the “link or path loss symmetry” where the path loss from access point to wireless node differs from the path loss from wireless node to access point by some fixed amount due to propagation characteristics, vantage point, and the like. In addition, sources of RF interference typically have unknown transmit powers, and may only partially overlap the frequency band in which wireless nodes operate. Estimating the location of these interference sources requires a method that does not depend entirely on the absolute detected signal strength value.
In light of the foregoing, a need in the art exists for a wireless node location mechanism that reduces the errors in computing the location of a wireless node due to errors in signal strength detection. A need in the art also exists for a wireless node location mechanism that reduces the errors in computing the location of a wireless node due to commonly occurring circumstances, such as variations in wireless node transmit power, errors in signal strength detection, and/or direction-dependent path loss. Embodiments of the present invention substantially fulfill these needs.